//回调函数类型定义
export type Indexer = (len: number, idx: number) => number;
// 实现获取从左到右的索引号
export function IndexerL2R(len: number, idx: number): number {
    return idx;
}
// 实现获取从右到左的索引号
export function IndexerR2L(len: number, idx: number): number {
    return (len - idx - 1);
}
export type NodeCallback<T> = (node: TreeNode<T>) => void;

export default class TreeNode<T>{
    /*
                                 树数据结构
           -------------------------root--------------------
          /                         |                      \
       node1                       node2                  node3
     /   |   \                    /      \                  |
node4  node5 node6              node7   node8             node9
   |                            |         |
 node10                        node11  node12
                                          |
                                        node13
   */
    // 父子节点的存储方式：
    private _parent: TreeNode<T> | undefined;        // 指向当前节点的父亲节点，如果this是根节点，则指向undefined，因为根节点肯定没有父亲节点
    private _children: Array<TreeNode<T>> | undefined; // 数组中保存所有直接儿子节点，如果是叶子节点，则_children为undefined或_children.length = 0
    public name: string;     // 当前节点的名称，有利于debug时信息输出或按名字获取节点（集合）操作
    public data: T | undefined;    // 一个泛型对象，指向一个需要依附到当前节点的对象

    public get root(): TreeNode<T> | undefined {
        let curr: TreeNode<T> | undefined = this;
        // 从this开始，一直向上遍历
        while (curr !== undefined && curr.parent !== undefined) {
            curr = curr.parent;
        }

        return curr;
    }

    public get depth(): number {
        let curr: TreeNode<T> | undefined = this;
        let level: number = 0;
        while (curr !== undefined && curr.parent !== undefined) {
            curr = curr.parent;
            level++;
        }
        return level;
    }

    public get parent(): TreeNode<T> | undefined {
        return this._parent;
    }

    public get children(): Array<TreeNode<T>> | undefined {
        return this._children;
    }

    // 获取当前节点的第一个儿子节点
    public get firstChild(): TreeNode<T> | undefined {
        // 如果当前节点存在儿子节点，返回第一个儿子节点，否则，返回undefined
        if (this._children !== undefined && this._children.length > 0) {
            return this._children[0];
        } else {
            return undefined;
        }
    }
    // 获取当前节点的最后一个儿子节点
    public get lastChild(): TreeNode<T> | undefined {
        if (this._children !== undefined && this._children.length > 0) {
            return this._children[this._children.length - 1];
        } else {
            return undefined;
        }
    }

    // 获取当前节点右兄弟（nextSibling）
    public get nextSibling(): TreeNode<T> | undefined {
        // 没有父亲节点，肯定没有兄弟节点
        if (this._parent === undefined) {
            return undefined;
        }
        // 只有当前节点的父亲节点的儿子节点的数量大于1才说明有兄弟节点
        // 如果只有1，就是this啦，不可能有兄弟节点
        if (this._parent._children !== undefined && this._parent._children.length > 1) {
            // 此时只说明可能有兄弟节点，还要知道是否有右兄弟节点
            // 先要知道当前节点在父亲节点的子节点列表中的索引号
            let idx: number = -1;
            for (let i = 0; i < this._parent._children.length; i++) {
                if (this === this._parent._children[i]) {
                    idx = i;
                    break;
                }
            }
            // idx 肯定不为-1
            // 如果idx不是父亲节点子节点列表中最后一个，说明有nextSibling
            if (idx !== this._parent._children.length - 1) {
                return this._parent._children[idx + 1];
            } else {
                // 说明当前节点在父亲节点的子列表的最后一个，不可能有右兄弟节点了
                return undefined;
            }
        } else {
            return undefined;
        }
    }
    // 获取当前节点左兄弟（prevSibling）
    public get prevSibling(): TreeNode<T> | undefined {
        // 没有父亲节点，肯定没有兄弟节点
        if (this._parent === undefined) {
            return undefined;
        }
        // 只有当前节点的父亲节点的儿子节点的数量大于1才说明有兄弟节点
        // 如果只有1，就是this啦，不可能有兄弟节点
        if (this._parent._children !== undefined && this._parent._children.length > 1) {
            // 此时只说明可能有兄弟节点，还要知道是否有右兄弟节点
            // 先要知道当前节点在父亲节点的子节点列表中的索引号
            let idx: number = - 1;
            for (let i = 0; i < this._parent._children.length; i++) {
                if (this === this._parent._children[i]) {
                    idx = i;
                    break;
                }
            }
            // idx 肯定不为-1
            // 如果idx不是父亲节点子节点列表中最前一个的话，说明有nextSibling
            if (idx !== 0) {
                return this._parent._children[idx - 1];
            } else {
                // 说明当前节点在父亲的子列表的最前一个，不可能有左兄弟了
                return undefined;
            }
        } else {
            return undefined;
        }
    }
    // 获取当前节点最右侧（mostRight）
    public get mostRight(): TreeNode<T> | undefined {
        let node: TreeNode<T> | undefined = this;
        // 以深度优先方式，不断调用lastChild，直到最后一个lastChild，肯定是最左子孙节点
        while (true) {
            let subNode: TreeNode<T> | undefined = undefined;
            if (node !== undefined) {
                // 调用lastChild只读属性
                subNode = node.lastChild;
            }
            if (subNode === undefined) {
                break;
            }
            node = subNode;
        }
        return node;
    }
    // 获取当前节点最左侧（mostLeft）
    public get mostLeft(): TreeNode<T> | undefined {
        let node: TreeNode<T> | undefined = this;
        // 以深度优先方式，不断调用firstChild，直到最后一个firstChild，肯定是最左子孙节点
        while (true) {
            let subNode: TreeNode<T> | undefined = undefined;
            if (node !== undefined) {
                // 调用firstChild只读属性
                subNode = node.firstChild;
            }
            if (subNode === undefined) {
                break;
            }
            node = subNode;
        }
        return node;
    }


    /**
     * 
     * @param data { T | undefined } 设置要创建的树节点上依附的数据T，默认为undefined
     * @param parent  { parent: TreeNode < T > | undefined = undefined } 设置要创建的树节点的父亲节点，默认为undefined
     * @param name { string } 设置要创建的树节点的名称，默认为空字符串
     */
    public constructor(data: T | undefined = undefined, parent: TreeNode<T> | undefined = undefined, name: string = "") {
        this._parent = parent;
        this._children = undefined;
        this.name = name;
        this.data = data;
        // 如果有父亲节点，则将this节点添加到父亲节点的儿子列表中
        if (this._parent !== undefined) {
            this._parent.addChild(this);
        }
    }

    /**
     * *判断一个要添加节点是否是当前节点的祖先节点
     * @param ancestor {TreeNode<T> | undefined}用于测试参数ancestor是this节点的祖先
     * @returns {boolean} 如果this节点是ancestor的子孙节点，返回true，否则，返回false
     */
    public isDescendantOf(ancestor: TreeNode<T> | undefined): boolean {
        // undefined值检查
        if (ancestor === undefined) return false;
        // 从当前节点的父亲节点开始向上遍历
        let node: TreeNode<T> | undefined = this._parent;
        for (let node: TreeNode<T> | undefined = this._parent; node !== undefined; node = node._parent) {
            // 如果当前节点的祖先等于ancestor，说明当前节点是ancestor的子孙，返回true
            if (node === ancestor) return true;
        }
        // 否则遍历完成，说明当前节点不是ancestor的子孙，返回false
        return false;
    }

    /**
     * *移除某个节点
     * @param index {number}要移除的子节点的索引号
     * @returns {TreeNode<T> | undefined}如果移除成功，返回的就是参数child节点，否则，为undefined
     */
    public removeChildAt(index: number): TreeNode<T> | undefined {
        //由于使用延迟初始化，必须要进行undefined值检查
        if (this._children === undefined) return undefined;
        // 根据索引从_children数组中获取节点
        let child: TreeNode<T> | undefined = this.getChildAt(index);
        //索引可能会越界，这是在getChildAt函数中处理的
        //如果索引越界了，getChildAt函数返回undefined
        //因此必须要进行undefined值检查
        if (child === undefined) return undefined;
        // TypeScript / js splice方法: 向/从数组中添加/删除项目，然后返回被删除的项目
        // 参数:
        // index必需。整数，规定添加/删除项目的位置，使用负数可从数组结尾处规定位置
        // howmany必需。要删除的项目数量。如果设置为 0，则不会删除项目
        // item1 , ... , itemX可选。向数组添加的新项目
        // 这里使用了index和howmany这两个参数，含义是:将index处的元素删除
        this._children.splice(index, 1); // 从子节点列表中移除掉
        child._parent = undefined; // 将子节点的父亲节点设置为undefined
        return child;

    }

    /**
     * 
     * @param child {TreeNode<T> | undefined}要移除的子节点
     * @returns {TreeNode<T> | undefined}如果移除成功，返回的就是参数child节点，否则为null
     */
    public removeChild(child: TreeNode<T | undefined>): TreeNode<T> | undefined {
        // 参数为undefined的处理
        if (child === undefined) return undefined;
        // 如果当前节点是叶子节点的处理
        if (this._children === undefined) return undefined;
        // 由于使用数组线性存储方式，从索引查找元素是最快的
        // 但是从元素查找索引，必须遍历整个数组
        let index: number = -1;
        for (let i: number = 0; i < this._children.length; i++) {
            if (this.getChildAt(i) === child) {
                index = i; // 找到要删除的子节点，记录索引
                break;
            }
        }
        //没有找到索引
        if (index === -1) return undefined;
        //找到要移除的子节点的索引，那么就调用removeChildAt方法
        return this.removeChildAt(index);
    }
    /**
     * *将this节点从父节点中移除
     * @returns { TreeNode < T > | undefined } 如果移除成功，返回的就是this节点
     */
    public remove(): TreeNode<T> | undefined {
        if (this._parent !== undefined) {
            return this._parent.removeChild(this);
        }
        return undefined;
    }

    /**
     * *从当前节点中获取索引指向的儿子节点
     * @param index {number} 要获取子节点的索引号
     * @returns {TreeNode<T> | undefined}如果获取成功，返回获取的子节点，否则，为undefined
     */
    public getChildAt(index: number): TreeNode<T> | undefined {
        if (this._children === undefined)
            return undefined;
        if (index < 0 || index >= this._children.length)
            return undefined;
        return this._children[index];
    }

    /**
     * *获取当前节点的儿子个数
     */
    public get childCount(): number {
        if (this._children !== undefined) {
            return this._children.length;
        }
        else {
            return 0;
        }
    }
    /**
     * *判断当前节点是否有儿子节点
     */
    public hasChild(): boolean {
        return this._children !== undefined && this._children.length > 0;
    }

    /**
     * *简便方法，在子列表最后添加一个儿子节点
     * @param child { TreeNode < T > } 要添加的子节点
     * @returns {TreeNode<T> | undefined}如果添加子节点成功，返回true，否则，返回false
     */
    public addChild(child: TreeNode<T>): TreeNode<T> | undefined {
        if (this._children === undefined) {
            this._children = [];
        }
        //在列表最后添加一个节点
        return this.addChildAt(child, this._children.length);
    }

    /**
     * 
     * @param child { TreeNode < T > } 要添加的子节点
     * @param index { number } 要添加到的索引位置
     * @returns {TreeNode<T> | undefined}如果添加子节点成功，返回true，否则，返回false
     */
    public addChildAt(child: TreeNode<T>, index: number): TreeNode<T> | undefined {
        // 第一种情况:要添加的子节点是当前节点的祖先的判断
        // 换句话说就是，当前节点已经是child节点的子孙节点，这样会循环引用，那就直接退出方法
        if (this.isDescendantOf(child)) {
            return undefined;
        }
        //延迟初始化的处理
        if (this._children === undefined) {
            //有两种方式初始化数组，笔者推荐[ ]方式，可以少写一些代码
            this._children = [];
            //this._children = new Array<TreeNode<T>>();
        }
        //索引越界检查
        if (index >= 0 && index <= this._children.length) {
            if (child._parent !== undefined) {
                //第二种情况:要添加的节点是有父亲节点的，需要从父亲节点中remove掉
                child._parent.removeChild(child);
            }
            //第三种情况: 要添加的节点不是当前节点的祖先并且也没有父亲节点(新节点或已从父亲移除)
            //设置父亲节点并添加到_children中
            child._parent = this;
            this._children.splice(index, 0, child);
            return child;
        }
        else {
            return undefined;
        }
    }

    /**
     * *将一个字符串输出n次
     * @param target {string}要重复输出的字符串
     * @param n {number}要输出多少次
     */
    public repeatString(target: string, n: number): string {
        let total: string = "";
        for (let i = 0; i < n; i++) {
            total += target;
        }
        return total;
    }

    /**
     * *以深度优先的方式递归遍历其子孙节点
     * @param preOrderFunc 
     * @param postOrderFunc 
     * @param indexFunc 
     */
    public visit(preOrderFunc: NodeCallback<T> | null = null, postOrderFunc: NodeCallback<T> | null = null, indexFunc: Indexer = IndexerL2R): void {
        // 在子节点递归调用visit之前，触发先根（前序）回调
        // 注意前序回调的时间点是在此处！！！！
        if (preOrderFunc !== null) {
            preOrderFunc(this);
        }
        // 遍历所有子节点
        let arr: Array<TreeNode<T>> | undefined = this._children;
        if (arr !== undefined) {
            for (let i: number = 0; i < arr.length; i++) {
                // 根据indexFunc选取左右遍历还是右左遍历
                let child: TreeNode<T> | undefined = this.getChildAt(indexFunc(arr.length, i));
                if (child !== undefined) {
                    // 递归调用visit
                    child.visit(preOrderFunc, postOrderFunc, indexFunc);
                }
            }
        }
        // 在这个时机点触发postOrderFunc回调
        // 注意后根（后序）回调的时间点是在此处！！！！
        if (postOrderFunc !== null) {
            postOrderFunc(this);
        }
    }

    public visitForward(preOrderFunc: NodeCallback<T> | null = null, postOrderFunc: NodeCallback<T> | null = null): void {
        if (preOrderFunc) {
            preOrderFunc(this);
        }
        let node: TreeNode<T> | undefined = this.firstChild;
        while (node !== undefined) {
            node.visitForward(preOrderFunc, postOrderFunc);
            node = node.nextSibling;
        }
        if (postOrderFunc) {
            postOrderFunc(this);
        }
    }

    public visitBackward(preOrderFunc: NodeCallback<T> | null = null, postOrderFunc: NodeCallback<T> | null = null): void {
        if (preOrderFunc) {
            preOrderFunc(this);
        }
        let node: TreeNode<T> | undefined = this.lastChild;
        while (node !== undefined) {
            node.visitBackward(preOrderFunc, postOrderFunc);
            node = node.prevSibling;
        }
        if (postOrderFunc) {
            postOrderFunc(this);
        }
    }

    public printLevelInfo(idx: number = 0): void {
        let str: string = this.repeatString(" ", idx * 4);
        let arr: Array<TreeNode<T>> | undefined = this._children;
        if (arr !== undefined) {
            for (let i: number = 0; i < arr.length; i++) {
                let child: TreeNode<T> | undefined = this.getChildAt(i);
                if (child !== undefined) {
                    child.printLevelInfo(idx + 1);
                }
            }
        }
        console.log("后根：" + str + this.name);
    }


    public printInfo(idx: number = 0): void {
        let str: string = this.repeatString(" ", idx * 4);
        console.log("先根：" + str + this.name);
        let node: TreeNode<T> | undefined = this.firstChild;
        while (node !== undefined) {
            node.printInfo(idx + 1);
            node = node.nextSibling;
        }
    }

    public printInfo2(idx: number = 0): void {
        let str: string = this.repeatString(" ", idx * 4);
        console.log("先根：" + str + this.name);
        let node: TreeNode<T> | undefined = this.lastChild;
        while (node !== undefined) {
            node.printInfo(idx + 1);
            node = node.prevSibling;
        }
    }

    public moveNext(): TreeNode<T> | undefined {
        let ret: TreeNode<T> | undefined = this.firstChild;
        if (ret !== undefined) {
            return ret;
        }
        ret = this.nextSibling;
        if (ret !== undefined) {
            return ret;
        }
        ret = this;
        while (ret !== undefined && ret.nextSibling === undefined) {
            ret = ret.parent;
        }
        if (ret !== undefined) {
            return ret.nextSibling;
        }
        return undefined;
    }

    public movePrev(): TreeNode<T> | undefined {
        let ret: TreeNode<T> | undefined = this.lastChild;
        if (ret !== undefined) {
            return ret;
        }
        ret = this.prevSibling;
        if (ret !== undefined) {
            return ret;
        }
        ret = this;
        while (ret !== undefined && ret.prevSibling === undefined) {
            ret = ret.parent;
        }
        if (ret !== undefined) {
            return ret.prevSibling;
        }
        return undefined;
    }

    public moveNextPost(): TreeNode<T> | undefined {
        let next: TreeNode<T> | undefined = this.nextSibling;
        if (next === undefined) {
            return this.parent;
        }

        let first: TreeNode<T> | undefined = undefined;
        while (next !== undefined && (first = next.firstChild)) {
            next = first;
        }

        return next;
    }

    public movePrevPost(): TreeNode<T> | undefined {
        let prev: TreeNode<T> | undefined = this.prevSibling;
        if (prev === undefined) {
            return this.parent;
        }
        let last: TreeNode<T> | undefined = undefined;
        while (prev !== undefined && (last = prev.lastChild)) {
            prev = last;
        }
        return prev;
    }
}